package sword.offer;

import sword.offer.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个 <b>二叉树</b>, 找到该树中两个指定节点的最近公共祖先。
 * 链接：https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class SixtyEightII {
    /**
     * 通过判断路径， 内存超时！
     */
    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            TreeNode val = null;
            List<TreeNode> pathA = getPath(root, new ArrayList<>(), p);
            List<TreeNode> pathB = getPath(root, new ArrayList<>(), q);
            for (int i = 0; i < Math.min(pathA.size(), pathB.size()); i++) {
                if (pathA.get(i).val != pathB.get(i).val) {
                    return val;
                }
                val = pathA.get(i);
            }
            return val;
        }

        private List<TreeNode> getPath(TreeNode curNode, List<TreeNode> path, TreeNode node) {
            if (curNode == null) {
                return path;
            }
            if (curNode.val == node.val) {
                path.add(curNode);
                return path;
            }
            path.add(curNode);
            List<TreeNode> path1 = getPath(curNode.left, new ArrayList<>(path), node);
            if (path1.get(path1.size() - 1).val == node.val) {
                return path1;
            }
            return getPath(curNode.right, new ArrayList<>(path), node);
        }

    }

    /**
     * 特别妙特别妙的一种递归方式。
     * 基本思路：
     * 如果左子树包含p或者q结点 并且 右子树也包含p或者q结点，那就说明当前结点就是公共结点。
     * or
     * 如果当前结点为p或者q 并且 当前结点的左子树 包含p或者q  or 当前结点的右子树 包含p或者q。那么当前结点就会公共祖先
     * */
    class Solution1 {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null || root == p || root == q){
                return root;
            }
            TreeNode l = lowestCommonAncestor(root.left,p, q);
            TreeNode r = lowestCommonAncestor(root.right,p, q);

            /*
             * 如果左子树找不到该节点 ,说明p和q都在右子树；
             * 如果右子树找不到该节点 ,说明p和q都在左子树；
             * 如果左子树和右子树都包含了p或者q，那么当前结点就是公共结点
             * */
            return l == null ? r : (r == null ? l : root);
        }
    }
}


